A packet processing device usually needs to buffer packets into a packet memory (PM) while the device processes them. The size of some packets (for example Ethernet packets) is not known in advance so the device needs to start storing the packet into the packet memory without knowing how large the packet is. Moreover, packets arrive at the device in an interleaved fashion, so the device is simultaneously storing several incoming packets into the packet buffer
The state of the art solution to store the packet in the device's memory is to assign multiple chunks (called pages) of packet memory to each packet, rather than a single big chunk. With this scheme, the packet is not stored consecutively in the packet memory, but rather is scattered in one or more pages throughout the packet memory. Therefore, a memory manager needs to maintain a linked list of all the pages that a particular packet uses in the packet memory; this linked list is traversed when the packet is read out of the packet memory for transmission.
FIG. 1 illustrates a Packet A with contents that are sequentially written in packet memory as Page Q, Page P, Page S and Page R. Each page has associated page state in a memory manager. As shown in FIG. 1, the page state may include:                A pointer to the next page;        Whether the page contains the start-of-packet (SOP) and/or the end-of-packet (EOP) attribute of the packet;        The valid bytes stored in the page (usually only relevant for the last page, where not all the page contains valid data);        . . . .        
The state of all the pages in the packet processor device is maintained by the memory manager. A packet has an associated descriptor that in its basic form is the pointer to the first page. With this initial pointer, all the pages used by the packet can be retrieved in the same order they were used by traversing the link list built from the next page pointers in the different page states.
Moreover, in a state of the art packet processing device, incoming packets are stored into the packet memory by a specialized direct-access memory (DMA) block (henceforth named Receive DMA or RDMA), and outgoing packets are retrieved from the packet memory by another DMA block (henceforth named Transmit DMA or TDMA).
FIG. 2 depicts the basic interaction between packet memory 200, TDMA 202, memory manager 204 and control elements 206. By way of example, the control elements may include a header processor, a header DMA, a transmission queue and the like. The three main functions of the control block are to perform any necessary modification of the packet, decide where to send the packet and perform any traffic management. For the purpose of this disclosure, the control block provides the packet descriptor to the TDMA, which is responsible from that point on to read the packet data from packet memory and send it out to the egress port.
The sequence of events is the following:                TDMA 202 is ready to send on a particular egress port, so TDMA requests 210 the control block for a descriptor for a packet to be sent to that egress port;        Control 206 sends the descriptor 212 if it has one;        TDMA 202 starts performing the page state link list walk by issuing requests 214 to the memory manager 204, which supplies page state 216;        For each page state, the TDMA 202 performs one or more requests 218 to the packet memory 200 to obtain the packet data 220; and        TDMA 202 sends the packet data to the egress port.        
FIG. 2 shows that the TDMA is responsible for performing the page link list walk, which requires, for each of the page states, a request (containing the page's pointer) to the memory manager, the memory manager reading the page state from its internal memory, and the memory manager returning the contents of the page state to the TDMA.
It is important to note that in order to request the state of the next page, the TDMA needs to have received the state of the current page (which contains the pointer to the next page). Therefore, there is a potentially large latency (in clock cycles) from the time the TDMA requests page state until it can request the next page state. FIG. 2 shows that this latency is twice Latency BT (for the request to the memory manager and for the return from the memory manager) plus Latency B (for the internal latency in the memory manager to obtain the page state).
This latency can become an issue depending on the size of the page and the speed (bits per second) of the egress port. The higher the speed of the port:                The higher the rate of return of page states to the TDMA needs to be;        The larger the page size (how much packet data each page holds) needs to be (however for small-size packets, a larger page size will not help);        The rate of page state returns (in clock cycles) is limited by several factors:        How far apart in the device (usually a chip) the TDMA and memory manager are; the farther apart, the higher the latency; and        The individual packet memory and TDMA latencies in reading the page state and requesting the next page, respectively.        
The page size is limited by the packet memory utilization: the larger the page size, the lower the packet memory utilization becomes because the percentage of a page that is not used increases with its size. This memory inefficiency becomes more prominent for small-size packets. Reducing the unused portion of the buffer memory by having smaller pages enables a smaller packet buffer, thus saving precious on-chip area for other packet processing functions.
Not meeting wire speed on an egress port is very undesirable because it translates into under run errors. An under run error occurs when a packet has started to be transmitted on a port and the driver of the packet data to the port (in this case the TDMA) fails to provide some of the data of the packet at the rate that is dictated by the speed of the port. When an under run error on a packet occurs, the receiving party discards the packet, and the same packet usually needs to be retransmitted again, causing performance degradation on the network.
Consequently, it is a strong requirement to meet the wire speed of the egress ports (so no under run errors occur), but it is non-trivial to achieve this goal given the implementation challenges of a high page state return rate and and/or a large page size.